package com.sicheng.algorithm.并查集;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/24 10:09
 */
public class 最长连续子序列 {
    private final HashMap<Integer, Integer> p = new HashMap<>();
    private final HashMap<Integer, Integer> counts = new HashMap<>();

    public int find(int x) {
        if (p.get(x) == x) {
            return x;
        }
        int pa = find(p.get(x));
        p.put(x, pa);
        return pa;
    }

    public void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);

        if (pa != pb) {
            p.put(pa, pb);
            counts.put(pb, counts.get(pa) + counts.get(pb));
        }
    }

    HashSet<Integer> set = new HashSet<>();

    void init(int[] nums) {
        for (int j : nums) {
            set.add(j);
            p.put(j, j);
            counts.put(j, 1);
        }
    }

    public int longest(int[] nums) {

        init(nums);

        for (int num : set) {
            if (set.contains(num - 1)) {
                union(num, num - 1);
            }
            if (set.contains(num + 1)) {
                union(num, num + 1);
            }
        }

        int max = -1;
        for (Integer integer : set) {
            max = Math.max(counts.get(integer), max);
        }

        return max;
    }

    public static void main(String[] args) {

    }
}
